package com.company.ljh.medium;


import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;


/**2542. 最大子序列的分数

 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/10/16 15:58
 * @version:1.0
 */

/**
 * 给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。
 *
 * 对于选择的下标 i0 ，i1 ，...， ik - 1 ，你的 分数 定义如下：
 *
 * nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。
 * 用公式表示： (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。
 * 请你返回 最大 可能的分数。
 *
 * 一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
 * 输出：12
 * 解释：
 * 四个可能的子序列分数为：
 * - 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。
 * - 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。
 * - 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。
 * - 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。
 * 所以最大分数为 12 。
 * 示例 2：
 *
 * 输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
 * 输出：30
 * 解释：
 * 选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。
 */
public class 最大子序列的分数 {
    public static Random random = new Random(System.currentTimeMillis());

    public long maxScore(int[] nums1, int[] nums2, int k) {
        int data[][] = new int[nums1.length][2];
        //两个数组组合成一个
        for (int i = 0; i < nums1.length; i++) {
            data[i][0] = nums1[i];
            data[i][1] = nums2[i];
        }
        PriorityQueue<Integer> minQueue = new PriorityQueue();
        //对nums2进行倒排序,使用自己写的排序算法会超时
        Arrays.sort(data, (a, b) -> b[1] - a[1]);
        long max = 0;
        long sum = 0;
        for (int i = 0; i < nums1.length; i++) {
            if (minQueue.size() == k - 1) {
                long result = (sum + data[i][0]) * data[i][1];
                max = Math.max(max, result);
                if (!minQueue.isEmpty() && minQueue.peek() < data[i][0]) {
                    //先出再近
                    sum = sum - minQueue.poll();
                    minQueue.offer(data[i][0]);
                    sum += data[i][0];
                }

            } else {
                minQueue.offer(data[i][0]);
                sum += data[i][0];
            }
        }
        return max;
    }

    //小根堆容量k版
    //定制化排序
    public static void fastSort(int sortNum[], int num[], int start, int end) {
        if (start >= end) {
            return;
        }
        int index = start + random.nextInt(end - start + 1);
        //获取数据
        int sourNumData = sortNum[index];
        int numData = num[index];
        //交换到第一个位置
        swapNum(sortNum, num, start, index);
        int startIndex = start;
        int endIndex = end;
        for (int i = start + 1; i <= endIndex; i++) {
            if (sortNum[i] >= sourNumData) {
                swapNum(sortNum, num, startIndex, i);
                startIndex++;
            } else {
                swapNum(sortNum, num, endIndex, i);
                //当前指针不变
                i--;
                endIndex--;
            }
        }
        fastSort(sortNum, num, start, startIndex - 1);
        fastSort(sortNum, num, endIndex + 1, end);

    }

    public static void swapNum(int sortNum[], int num[], int index1, int index2) {
        int temp = sortNum[index1];
        sortNum[index1] = sortNum[index2];
        sortNum[index2] = temp;
        //两边数组同步交换
        temp = num[index1];
        num[index1] = num[index2];
        num[index2] = temp;
    }
}
